package com.cheung.leetcode.hash;

import lyroot.entity.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class LC106 {

    static Map<Integer, Integer> hash = new HashMap<>();

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            hash.put(inorder[i], i);
        }
        return next(postorder, inorder.length - 1, 0, inorder.length - 1);
    }

    private static TreeNode next(int[] postorder, int root, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[root]);

        Integer i = hash.get(postorder[root]);

        node.left = next(postorder, root - 1 - right + i, left, i - 1);
        node.right = next(postorder, root - 1, i + 1, right);

        return node;
    }


    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7}, postorder = {9, 15, 7, 20, 3};
        TreeNode treeNode = buildTree(inorder, postorder);
    }
}
